SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Granularity (parallel computing)</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Granularity (parallel computing)</span></span>

</h1>

</header>

<p>In <a href="Parallel_computing" title="Parallel computing">parallel computing</a>, <b>granularity</b> (or <a href="Granulation" title="Granulation">grain</a> size) of a <a href="Task_(computing)" title="Task (computing)">task</a> is a measure of the amount of work (or <a href="Computation" title="Computation">computation</a>) which is performed by that task.<sup id="cite_ref-hwang_1-0" class="reference"><a href="#cite_note-hwang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>Another definition of granularity takes into account the communication <a href="Overhead_(computing)" title="Overhead (computing)">overhead</a> between multiple <a href="Processor_(computing)" title="Processor (computing)">processors</a> or processing elements. It defines granularity as the ratio of computation time to communication time, wherein computation time is the time required to perform the computation of a task and communication time is the time required to exchange data between processors.<sup id="cite_ref-Kwiatkowski_2-0" class="reference"><a href="#cite_note-Kwiatkowski-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>If <span class="texhtml"><i>T</i><sub>comp</sub></span> is the computation time and <span class="texhtml"><i>T</i><sub>comm</sub></span> denotes the communication time, then the granularity <span class="texhtml mvar" style="font-style:italic;">G</span> of a task can be calculated as:<sup id="cite_ref-Kwiatkowski_2-1" class="reference"><a href="#cite_note-Kwiatkowski-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G={\frac {T_{\mathrm {comp} }}{T_{\mathrm {comm} }}}}</annotation>

</semantics>

</math></span><img src="./8e2be9fc1ca77272ae6112ea7a50334720015139.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:11.641ex; height:5.843ex;" alt="{\displaystyle G={\frac {T_{\mathrm {comp} }}{T_{\mathrm {comm} }}}}" loading="lazy"></span></dd></dl></dd></dl>

<p>Granularity is usually measured in terms of the number of <a href="Instruction_set_architecture" title="Instruction set architecture">instructions</a> which are <a href="Execution_(computing)" title="Execution (computing)">executed</a> in a particular task.<sup id="cite_ref-hwang_1-1" class="reference"><a href="#cite_note-hwang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Alternately, granularity can also be specified in terms of the execution time of a program, combining the computation time and communication time.<sup id="cite_ref-hwang_1-2" class="reference"><a href="#cite_note-hwang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Types_of_parallelism">Types of parallelism</h2></div>

<p>Depending on the amount of work which is performed by a parallel task, parallelism can be classified into three categories: fine-grained, medium-grained and coarse-grained parallelism.

</p>

<div class="mw-heading mw-heading3"><h3 id="Fine-grained_parallelism">Fine-grained parallelism</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For more, see <a href="Microparallelism" title="Microparallelism">Microparallelism</a>.</div>

<p>In fine-grained parallelism, a program is broken down to a large number of small tasks. These tasks are assigned individually to many processors. The amount of work associated with a parallel task is low and the work is evenly distributed among the processors. Hence, fine-grained parallelism facilitates <a href="Load_balancing_(computing)" title="Load balancing (computing)">load balancing</a>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>As each task processes less data, the number of processors required to perform the complete processing is high. This in turn, increases the communication and synchronization overhead.

</p><p>Fine-grained parallelism is best exploited in architectures which support fast communication. <a href="Shared_memory" title="Shared memory">Shared memory</a> architecture which has a low communication overhead is most suitable for fine-grained parallelism.

</p><p>It is difficult for programmers to detect parallelism in a program, therefore, it is usually the <a href="Compiler" title="Compiler">compilers'</a> responsibility to detect fine-grained parallelism.<sup id="cite_ref-hwang_1-3" class="reference"><a href="#cite_note-hwang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>An example of a fine-grained system (from outside the parallel computing domain) is the system of <a href="Neurons" class="mw-redirect" title="Neurons">neurons</a> in our <a href="Brain" title="Brain">brain</a>.<sup id="cite_ref-Russ_4-0" class="reference"><a href="#cite_note-Russ-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p><p><a href="Connection_Machine" title="Connection Machine"><b>Connection Machine (CM-2)</b></a> and <b><a href="J-Machine" class="mw-redirect" title="J-Machine">J-Machine</a></b> are examples of fine-grain parallel computers that have grain size in the range of 4-5 μs.<sup id="cite_ref-hwang_1-4" class="reference"><a href="#cite_note-hwang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Coarse-grained_parallelism">Coarse-grained parallelism</h3></div>

<p>In coarse-grained parallelism, a program is split into large tasks. Due to this, a large amount of computation takes place in processors. This might result in load imbalance, wherein certain tasks process the bulk of the data while others might be idle. Further, coarse-grained parallelism fails to exploit the parallelism in the program as most of the computation is performed sequentially on a processor. The advantage of this type of parallelism is low communication and synchronization overhead.

</p><p><a href="Message-passing" class="mw-redirect" title="Message-passing">Message-passing</a> architecture takes a long time to communicate data among processes which makes it suitable for coarse-grained parallelism.<sup id="cite_ref-hwang_1-5" class="reference"><a href="#cite_note-hwang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p><b><a href="Cray_Y-MP" title="Cray Y-MP">Cray Y-MP</a></b> is an example of coarse-grained parallel computer which has a grain size of about 20s.<sup id="cite_ref-hwang_1-6" class="reference"><a href="#cite_note-hwang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Medium-grained_parallelism">Medium-grained parallelism</h3></div>

<p>Medium-grained parallelism is used relatively to fine-grained and coarse-grained parallelism. Medium-grained parallelism is a compromise between fine-grained and coarse-grained parallelism, where we have task size and communication time greater than fine-grained parallelism and lower than coarse-grained parallelism. Most general-purpose parallel computers fall in this category.<sup id="cite_ref-Russ_4-1" class="reference"><a href="#cite_note-Russ-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p><p><b><a href="Intel_iPSC" title="Intel iPSC">Intel iPSC</a></b> is an example of medium-grained parallel computer which has a grain size of about 10ms.<sup id="cite_ref-hwang_1-7" class="reference"><a href="#cite_note-hwang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>Consider a stack of 20 images with size 10x10 pixels that need to be processed, assuming that each of the 100 pixels can be processed independently of each other. Processing 1 pixel takes 1 clock cycle.

</p><p><b>Fine-grained parallelism:</b> Each pixel will be processed individually by one processor at a time. Assuming there are 100 processors that are responsible for processing the image, the 100 processors can process one 10x10 image in a single clock cycle. With 20 processors, it would take 5 clock cycles per image. Each processor can be utilized for 100% of its available time but the result of each pixel-computation needs to be communicated and aggregated at the end of each image processing which can cause a lot of overhead (100 communications per image = 2000 total).

</p><p><b>Medium-grained parallelism:</b> The images are split into quarters. Each quarter will be processed individually by one processor at a time taking 25 clock cycles (for 5x5 pixels). Assuming there are 20 processors that are responsible for processing the stack of 20 images, 5 images can be processed in parallel with 4 processors working on each image. If 100 processors were available, 80 could process the stack in parallel taking 25 clock cycles while 20 processors sit idle without any work assigned to them. Once the four quarters have been processed, the results must be aggregated (4 communications per image = 80 total).

</p><p><b>Coarse-grained parallelism:</b> A full image is processed by a single processor taking 100 clock cycles. In this case only 20 processors can be used at a time, completing the work in 100 clock cycles without any communication.

</p><p>The decision on which approach is best depends on the workload and available processing units. The goal should be to maximize parallelization (split work into enough units to evenly distribute it across most available processors) while minimizing communication overhead (ratio of time spend on communication vs time spend on computation). In our example, if the number of pictures to process is high compared to the number of workers, it does not make sense to break images down into smaller units since each worker will receive enough load. If the number of pictures is small compared to the number of workers, some workers might sit idle and waste computation time. However, this only is a problem if processing a single image takes a long time. If the processing is very fast then splitting the work into smaller units might make the total operation slower since the time lost to communication is more than the time gained through parallelization.

</p>

<div class="mw-heading mw-heading2"><h2 id="Levels_of_parallelism">Levels of parallelism</h2></div>

<p>Granularity is closely tied to the level of processing. A program can be broken down into 4 levels of parallelism -

</p>

<ol><li>Instruction level.</li>

<li>Loop level</li>

<li>Sub-routine level and</li>

<li>Program-level</li></ol>

<p>The highest amount of parallelism is achieved at <b>instruction</b> level, followed by <b>loop-level</b> parallelism. At instruction and loop level, fine-grained parallelism is achieved. Typical grain size at instruction-level is 20 instructions, while the grain-size at loop-level is 500 instructions.<sup id="cite_ref-hwang_1-8" class="reference"><a href="#cite_note-hwang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>At the <b>sub-routine</b> (or procedure) level the grain size is typically a few thousand instructions. Medium-grained parallelism is achieved at sub-routine level.<sup id="cite_ref-hwang_1-9" class="reference"><a href="#cite_note-hwang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>At <b>program-level</b>, parallel execution of programs takes place. Granularity can be in the range of tens of thousands of instructions.<sup id="cite_ref-hwang_1-10" class="reference"><a href="#cite_note-hwang-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Coarse-grained parallelism is used at this level.

</p><p>The below table shows the relationship between levels of parallelism, grain size and degree of parallelism

</p>

<th>Levels</th>

<th>Grain Size</th>

<th>Parallelism

</th></tr>

<tr>

<td style="width: 250px;">Instruction level</td>

<td style="width: 250px;">Highest

</td></tr>

<tr>

<td>Loop level</td>

<td>Moderate

</td></tr>

<tr>

<td>Sub-routine level</td>

<td>Medium</td>

<td>Moderate

</td></tr>

<tr>

<td>Program level</td>

<td>Coarse</td>

<td>Least

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Impact_of_granularity_on_performance">Impact of granularity on performance</h2></div>

<p>Granularity affects the performance of parallel computers. Using fine grains or small tasks results in more parallelism and hence increases the <a href="Speedup" title="Speedup">speedup</a>.

However, synchronization overhead, <a href="Scheduling" class="mw-redirect" title="Scheduling">scheduling</a> strategies etc. can negatively impact the performance of fine-grained tasks. Increasing parallelism alone cannot give the best performance.<sup id="cite_ref-chen_5-0" class="reference"><a href="#cite_note-chen-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p><p>In order to reduce the communication overhead, granularity can be increased. Coarse grained tasks have less communication overhead but they often cause load imbalance.

Hence optimal performance is achieved between the two extremes of fine-grained and coarse-grained parallelism.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p><p>Various studies<sup id="cite_ref-chen_5-1" class="reference"><a href="#cite_note-chen-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> have proposed their solution to help determine the best granularity to aid parallel processing. Finding the best grain size, depends on a number of factors and varies greatly from problem-to-problem.

</p>

<ul><li><a href="Instruction-level_parallelism" title="Instruction-level parallelism">Instruction-level parallelism</a></li>

<li><a href="Data_Parallelism" class="mw-redirect" title="Data Parallelism">Data Parallelism</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Citations">Citations</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFHwang1992" class="citation book cs1">Hwang, Kai (1992). <a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=541880&preflayout=flat"><i>Advanced Computer Architecture: Parallelism, Scalability, Programmability</i></a> (1st ed.). McGraw-Hill Higher Education. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0070316225</bdi>.</cite></span>

</li>

<li id="cite_note-Kwiatkowski-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-Kwiatkowski_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Kwiatkowski_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFKwiatkowski2001" class="citation book cs1">Kwiatkowski, Jan (9 September 2001). "Evaluation of Parallel Programs by Measurement of Its Granularity". <i>Parallel Processing and Applied Mathematics</i>. Lecture Notes in Computer Science. Vol. 2328. pp. <span class="nowrap">145–</span>153. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-48086-2_16">10.1007/3-540-48086-2_16</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540437925</bdi>.</cite> <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540480860</bdi>.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFBarney" class="citation book cs1">Barney, Blaise. <a rel="nofollow" class="external text" href="https://computing.llnl.gov/tutorials/parallel_comp"><i>Introduction to Parallel Computing</i></a>.</cite></span>

</li>

<li id="cite_note-Russ-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-Russ_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Russ_4-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFMillerStout1996" class="citation book cs1">Miller, Russ; Stout, Quentin F. (1996). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Ub-VzON_O2wC&dq=medium-grained+machine&pg=PA5"><i>Parallel Algorithms for Regular Architectures: Meshes and Pyramids</i></a>. Cambridge, Mass.: MIT Press. pp. <span class="nowrap">5–</span>6. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780262132336</bdi>.</cite></span>

</li>

<li id="cite_note-chen-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-chen_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-chen_5-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFChenSuYew1990" class="citation book cs1">Chen, Ding-Kai; Su, Hong-Men; Yew, Pen-Chung (1 January 1990). "The impact of synchronization and granularity on parallel systems". <i>Proceedings of the 17th annual international symposium on Computer Architecture - ISCA '90</i>. Vol. 18. pp. <span class="nowrap">239–</span>248. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.3389">10.1.1.51.3389</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F325164.325150">10.1145/325164.325150</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-89791-366-3</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16193537">16193537</a>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFYeungDallyAgarwal" class="citation journal cs1">Yeung, Donald; Dally, William J.; Agarwal, Anant. "How to Choose the Grain Size of a Parallel Computer". <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.3298">10.1.1.66.3298</a></span>.</cite> <span class="cs1-visible-error citation-comment"><code class="cs1-code">{{cite journal}}</code>: </span><span class="cs1-visible-error citation-comment">Cite journal requires <code class="cs1-code">|journal=</code> (help)</span></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFMcCrearyGill1989" class="citation journal cs1">McCreary, Carolyn; Gill, Helen (1 September 1989). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F66451.66454">"Automatic Determination of Grain Size for Efficient Parallel Processing"</a>. <i>Commun. ACM</i>. <b>32</b> (9): <span class="nowrap">1073–</span>1078. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F66451.66454">10.1145/66451.66454</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0001-0782">0001-0782</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14807217">14807217</a>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFKruatrachueLewis1988" class="citation journal cs1">Kruatrachue, Boontee; Lewis, Ted (1 January 1988). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=624686">"Grain Size Determination for Parallel Processing"</a></span>. <i>IEEE Softw</i>. <b>5</b> (1): <span class="nowrap">23–</span>32. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F52.1991">10.1109/52.1991</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0740-7459">0740-7459</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2034255">2034255</a>.</cite></span>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Parallel_computing346" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Parallel_computing346" style="font-size:114%;margin:0 4em"><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Distributed_computing" title="Distributed computing">Distributed computing</a></li>

<li><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></li>

<li><a href="Parallel_algorithm" title="Parallel algorithm">Parallel algorithm</a></li>

<li><a href="Massively_parallel" title="Massively parallel">Massively parallel</a></li>

<li><a href="Cloud_computing" title="Cloud computing">Cloud computing</a></li>

<li><a href="High-performance_computing" title="High-performance computing">High-performance computing</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li>

<li><a href="Manycore_processor" title="Manycore processor">Manycore processor</a></li>

<li><a href="General-purpose_computing_on_graphics_processing_units" title="General-purpose computing on graphics processing units">GPGPU</a></li>

<li><a href="Computer_network" title="Computer network">Computer network</a></li>

<li><a href="Systolic_array" title="Systolic array">Systolic array</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Levels</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Instruction-level_parallelism" title="Instruction-level parallelism">Instruction</a></li>

<li><a href="Task_parallelism" title="Task parallelism">Thread</a></li>

<li><a href="Memory-level_parallelism" title="Memory-level parallelism">Memory</a></li>

<li><a href="Pipeline_(computing)" title="Pipeline (computing)">Pipeline</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Multithreading_(computer_architecture)" title="Multithreading (computer architecture)">Multithreading</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Temporal_multithreading" title="Temporal multithreading">Temporal</a></li>

<li><a href="Simultaneous_multithreading" title="Simultaneous multithreading">Simultaneous</a> (SMT)</li>

<li><a href="Simultaneous_and_heterogeneous_multithreading" title="Simultaneous and heterogeneous multithreading">Simultaneous and heterogenous</a></li>

<li><a href="Speculative_multithreading" title="Speculative multithreading">Speculative</a> (SpMT)</li>

<li><a href="Preemption_(computing)" title="Preemption (computing)">Preemptive</a></li>

<li><a href="Computer_multitasking#Cooperative_multitasking" title="Computer multitasking">Cooperative</a></li>

<li><a href="Bulldozer_(microarchitecture)#Bulldozer_core" title="Bulldozer (microarchitecture)">Clustered multi-thread</a> (CMT)</li>

<li><a href="Hardware_scout" title="Hardware scout">Hardware scout</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theory</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parallel_RAM" title="Parallel RAM">PRAM model</a></li>

<li><a href="Parallel_external_memory" title="Parallel external memory">PEM model</a></li>

<li><a href="Analysis_of_parallel_algorithms" title="Analysis of parallel algorithms">Analysis of parallel algorithms</a></li>

<li><a href="Amdahl's_law" title="Amdahl's law">Amdahl's law</a></li>

<li><a href="Gustafson's_law" title="Gustafson's law">Gustafson's law</a></li>

<li><a href="Cost_efficiency" title="Cost efficiency">Cost efficiency</a></li>

<li><a href="Karp%E2%80%93Flatt_metric" title="Karp–Flatt metric">Karp–Flatt metric</a></li>

<li><a href="Parallel_slowdown" title="Parallel slowdown">Slowdown</a></li>

<li><a href="Speedup" title="Speedup">Speedup</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Elements</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Process_(computing)" title="Process (computing)">Process</a></li>

<li><a href="Thread_(computing)" title="Thread (computing)">Thread</a></li>

<li><a href="Fiber_(computer_science)" title="Fiber (computer science)">Fiber</a></li>

<li><a href="Instruction_window" title="Instruction window">Instruction window</a></li>

<li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Coordination</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li>

<li><a href="Memory_coherence" title="Memory coherence">Memory coherence</a></li>

<li><a href="Cache_coherence" title="Cache coherence">Cache coherence</a></li>

<li><a href="Cache_invalidation" title="Cache invalidation">Cache invalidation</a></li>

<li><a href="Barrier_(computer_science)" title="Barrier (computer science)">Barrier</a></li>

<li><a href="Synchronization_(computer_science)" title="Synchronization (computer science)">Synchronization</a></li>

<li><a href="Application_checkpointing" title="Application checkpointing">Application checkpointing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_programming" title="Computer programming">Programming</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Stream_processing" title="Stream processing">Stream processing</a></li>

<li><a href="Dataflow_programming" title="Dataflow programming">Dataflow programming</a></li>

<li><a href="Parallel_programming_model" title="Parallel programming model">Models</a>

<ul><li><a href="Implicit_parallelism" title="Implicit parallelism">Implicit parallelism</a></li>

<li><a href="Explicit_parallelism" title="Explicit parallelism">Explicit parallelism</a></li>

<li><a href="Concurrency_(computer_science)" title="Concurrency (computer science)">Concurrency</a></li></ul></li>

<li><a href="Non-blocking_algorithm" title="Non-blocking algorithm">Non-blocking algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_hardware" title="Computer hardware">Hardware</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Flynn's_taxonomy" title="Flynn's taxonomy">Flynn's taxonomy</a>

<ul><li><a href="Single_instruction%2C_multiple_threads" title="Single instruction, multiple threads">Array processing</a> (SIMT)</li>

<li><a href="Flynn's_taxonomy#Pipelined_processor" title="Flynn's taxonomy">Pipelined processing</a></li>

<li><a href="Flynn's_taxonomy#Associative_processor" title="Flynn's taxonomy">Associative processing</a></li></ul></li>

<li><a href="Dataflow_architecture" title="Dataflow architecture">Dataflow architecture</a></li>

<li><a href="Instruction_pipelining" title="Instruction pipelining">Pipelined processor</a></li>

<li><a href="Superscalar_processor" title="Superscalar processor">Superscalar processor</a></li>

<li><a href="Vector_processor" title="Vector processor">Vector processor</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessor</a>

<ul><li><a href="Symmetric_multiprocessing" title="Symmetric multiprocessing">symmetric</a></li>

<li><a href="Asymmetric_multiprocessing" title="Asymmetric multiprocessing">asymmetric</a></li></ul></li>

<li><a href="Semiconductor_memory" title="Semiconductor memory">Memory</a>

<ul><li><a href="Shared_memory" title="Shared memory">shared</a></li>

<li><a href="Distributed_memory" title="Distributed memory">distributed</a></li>

<li><a href="Distributed_shared_memory" title="Distributed shared memory">distributed shared</a></li>

<li><a href="Massively_parallel" title="Massively parallel">Massively parallel</a> computer</li>

<li><a href="Computer_cluster" title="Computer cluster">Computer cluster</a>

<ul><li><a href="Beowulf_cluster" title="Beowulf cluster">Beowulf cluster</a></li></ul></li>

<li><a href="Grid_computing" title="Grid computing">Grid computer</a></li>

<li><a href="Hardware_acceleration" title="Hardware acceleration">Hardware acceleration</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="API" title="API">APIs</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ateji_PX" title="Ateji PX">Ateji PX</a></li>

<li><a href="Boost_(C%2B%2B_libraries)" title="Boost (C++ libraries)">Boost</a></li>

<li><a href="Chapel_(programming_language)" title="Chapel (programming language)">Chapel</a></li>

<li><a href="Charm%2B%2B" title="Charm++">Charm++</a></li>

<li><a href="Coarray_Fortran" title="Coarray Fortran">Coarray Fortran</a></li>

<li><a href="Dryad_(programming)" title="Dryad (programming)">Dryad</a></li>

<li><a href="Global_Arrays" title="Global Arrays">Global Arrays</a></li>

<li><a href="GPUOpen" title="GPUOpen">GPUOpen</a></li>

<li><a href="OpenMP" title="OpenMP">OpenMP</a></li>

<li><a href="OpenCL" title="OpenCL">OpenCL</a></li>

<li><a href="OpenHMPP" title="OpenHMPP">OpenHMPP</a></li>

<li><a href="OpenACC" title="OpenACC">OpenACC</a></li>

<li><a href="Parallel_Extensions" title="Parallel Extensions">Parallel Extensions</a></li>

<li><a href="Pthreads" title="Pthreads">pthreads</a></li>

<li><a href="RaftLib" title="RaftLib">RaftLib</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Problems</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatic_parallelization" title="Automatic parallelization">Automatic parallelization</a></li>

<li><a href="Deadlock_(computer_science)" title="Deadlock (computer science)">Deadlock</a></li>

<li><a href="Deterministic_algorithm" title="Deterministic algorithm">Deterministic algorithm</a></li>

<li><a href="Embarrassingly_parallel" title="Embarrassingly parallel">Embarrassingly parallel</a></li>

<li><a href="Parallel_slowdown" title="Parallel slowdown">Parallel slowdown</a></li>

<li><a href="Race_condition" title="Race condition">Race condition</a></li>

<li><a href="Software_lockout" title="Software lockout">Software lockout</a></li>

<li><a href="Scalability" title="Scalability">Scalability</a></li>

<li><a href="Starvation_(computer_science)" title="Starvation (computer science)">Starvation</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category: Parallel computing</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-26" href="https://en.wikipedia.org/wiki/?title=Granularity_(parallel_computing)&oldid=1292249392">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>